colors = [['red', 'green', 'green', 'red' , 'red'],
          ['red', 'red', 'green', 'red', 'red'],
          ['red', 'red', 'green', 'green', 'red'],
          ['red', 'red', 'red', 'red', 'red']]

measurements = ['green', 'green', 'green' ,'green', 'green']

motions = [[0,0],[0,1],[1,0],[1,0],[0,1]]

sensor_right = 0.7

p_move = 0.8

def show(p):
    for i in range(len(p)):
        print p[i]

#DO NOT USE IMPORT
#ENTER CODE BELOW HERE
#ANY CODE ABOVE WILL CAUSE
#HOMEWORK TO BE GRADED
#INCORRECT

total_cells = len(colors) * len(colors[0]) 
p = []
# init p to the size of the world with equal probabilities
for r in range(len(colors)):
    new_row = []
    for c in range(len(colors[r])):
        new_row.append(1.0/total_cells)
    p.append(new_row)
    
def sense(p, Z):
    q=[]
    cell_sum = 0.0
    for r in range(len(p)):
        new_row = []
        for c in range(len(p[r])):
            # determine if there is a macth to the sensor measurment
            hit = (Z == colors[r][c])
            # calculate the new p value based on the probabilities
            new_row.append(p[r][c] * ((hit * sensor_right) + ((1-hit) * (1-sensor_right))))
        q.append(new_row)
        cell_sum = sum(new_row) + cell_sum
    
    # normalize the probabilities
    for r in range(len(q)):
        for c in range(len(q[r])):
            q[r][c] = q[r][c] / cell_sum
    return q

def move(p, U):
    q = []
    for r in range(len(p)):
        new_row = []
        for c in range(len(p[r])):
            # add value to describe probablility of no movement
            move_value = ((1.0-p_move) * p[(r) % len(p)][(c) % len(p[r])])
             # add value to describe probablility of correct movement
            move_value = move_value + (p_move * p[(r-U[0]) % len(p)][(c-U[1]) % len(p[r])])
            new_row.append(move_value)
        q.append(new_row)
    return q
    
for k in range(len(measurements)):
    p = move(p, motions[k])
    p = sense(p, measurements[k])
   
#Your probability array must be printed 
#with the following code.

show(p)





